本篇同步發布於Blog:[解題] LeetCode - 125 Valid Palindrome

平台：

LeetCode

題號：

125 - Valid Palindrome

題目連結：

https://leetcode.com/problems/valid-palindrome/

題目說明：

        給1個字串s，求s是否為s的palindrome(回文)，這題的Palindrome的定義是字串的英文字母和數字是左右對稱，且英文大小寫不分，如果是其他字元則略過不比對。

比如範例輸入s = "A man, a plan, a canal: Panama"，它扣掉空白、逗號、分號，全轉成小寫的話，會是"amanaplanacanalpanama"，會是左右對稱的回文。

特殊案例是 s = ",!"，全都只有標點符號，這也是回文。

解題方法：

   　 建立2個索引值i和j，分別從字串s的左邊和右邊掃描，找到第1個英文字母或數字則停下，確認是否符合回文定義的比對規則，如果不相同，則並不是回文。當i >= j，代表已經都比對完，則屬於回文。

而判斷是否相同字母或數字，可以用字元的ASCII範圍檢查，並回傳自定義的索引值，比如'A'和'a'回傳0、'0'回傳26(與前面英文字母不同)。

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
using namespace std;

class Solution {
private: 
    int getAlphanumericCommonIndex(char c){
        int index;
        if(c >= 'a' && c <= 'z'){
            index = c - 'a';
        }
        else if(c >= 'A' && c <= 'Z'){
            index = c - 'A';
        }
        else{
            index = c - '0' + 26;
        }
        
        return index;
    }
public:
    bool isPalindrome(string s) {
        int n = s.length();
        int i = 0, j = n-1;
        bool isOk = true;
        int left, right;
        while(i < j){
            while(i < n && !(s[i] >= '0' && s[i] <= '9') && !(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= 'A' && s[i] <= 'Z')){
                ++i;
            }
            
            while(j >= 0 && !(s[j] >= '0' && s[j] <= '9') && !(s[j] >= 'a' && s[j] <= 'z') && !(s[j] >= 'A' && s[j] <= 'Z')){
                --j;
            }

            if(i >= j){
                break;
            }
            
            left = getAlphanumericCommonIndex(s[i]);
            right = getAlphanumericCommonIndex(s[j]);

            
            if(left != right){
                isOk = false;
                break;
            }
            
            ++i;
            --j;
        }
        
        return isOk;
    }
};

int main() {
	Solution sol;
	cout << sol.isPalindrome("A man, a plan, a canal: Panama") << endl;
	cout << sol.isPalindrome("race a car") << endl;
	return 0;
}

using System;

namespace LeetCode125
{
	public class Solution {
	    private int GetAlphanumericCommonIndex(char c){
	        int index;
	        if(c >= 'a' && c <= 'z'){
	            index = c - 'a';
	        }
	        else if(c >= 'A' && c <= 'Z'){
	            index = c - 'A';
	        }
	        else{
	            index = c - '0' + 26;
	        }
	        
	        return index;
	    }
	    
	    public bool IsPalindrome(string s) {
	        int n = s.Length;
	        int i = 0, j = n-1;
	        bool isOk = true;
	        int left, right;
	        while(i < j){
	            while(i < n && !(s[i] >= '0' && s[i] <= '9') && !(s[i] >= 'a' && s[i] <= 'z') && !(s[i] >= 'A' && s[i] <= 'Z')){
	                ++i;
	            }
	            
	            while(j >= 0 && !(s[j] >= '0' && s[j] <= '9') && !(s[j] >= 'a' && s[j] <= 'z') && !(s[j] >= 'A' && s[j] <= 'Z')){
	                --j;
	            }
	
	            if(i >= j){
	                break;
	            }
	            
	            left = GetAlphanumericCommonIndex(s[i]);
	            right = GetAlphanumericCommonIndex(s[j]);
	
	            
	            if(left != right){
	                isOk = false;
	                break;
	            }
	            
	            ++i;
	            --j;
	        }
	        
	        return isOk;
	    }
	}
	
	public class Program
	{
		public static void Main()
		{
			Solution sol = new Solution();
			Console.WriteLine(sol.IsPalindrome("A man, a plan, a canal: Panama"));
			Console.WriteLine(sol.IsPalindrome("race a car"));
			Console.Read();
		}
	}
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/100-199/125.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/100-199/125.cs